PC Media 7/PC MEDIA CD07.iso/share/prog/cm/cmtordar.cc

C/C++ Source or Header | 1994-09-06 | 7.1 KB | 317 lines

// CmTOrdAr.cc
// -----------------------------------------------------------------
// Compendium - C++ Container Class Library
// Copyright (C) 1992-1994, Glenn M. Poorman, All rights reserved
// -----------------------------------------------------------------
// Ordered array template implementation.
// -----------------------------------------------------------------


// "CmTOrderedArray" is the default array constructor.
//
template <class T>
CmTOrderedArray<T>::CmTOrderedArray(unsigned sz, unsigned dt)
{
  _delta   = dt;
  _total   = 0;
  _entries = (sz > 0) ? new T[sz] : NULL;
  _size    = (_entries != NULL) ? sz : 0;
}


// "CmTOrderedArray" is the array copy constructor.
//
template <class T>
CmTOrderedArray<T>::CmTOrderedArray(const CmTOrderedArray<T>& A)
                  : CmTContainer<T>(A)
{
  _total   = 0;
  _entries = NULL;
  copy(A);
}


// "=" assignment operator copies the specified array into this array.
//
template <class T>
CmTOrderedArray<T>& CmTOrderedArray<T>::operator=(const CmTOrderedArray<T>& A)
{
  if (&A != this) copy(A);
  return *this;
}


// "delta" sets a new delta value for automatic growing.
//
template <class T> void CmTOrderedArray<T>::delta(unsigned dt)
{
  _delta = dt;
}


// "delta" returns the current delta value.
//
template <class T> unsigned CmTOrderedArray<T>::delta() const
{
  return _delta;
}


// "total" returns the number of items in the array.
//
template <class T> int CmTOrderedArray<T>::total() const
{
  return _total;
}


// "at" returns the item at the specified index.
//
template <class T> const T& CmTOrderedArray<T>::at(int idx) const
{
  return _entries[idx];
}


// "[]" returns the item at the specified index.
//
template <class T> const T& CmTOrderedArray<T>::operator[](int idx) const
{
  return at(idx);
}


// "add" appends the specified item to this array.
//
template <class T> Bool CmTOrderedArray<T>::add(const T& rObj)
{
  if (_total >= _size)
    if (_delta == 0 || !resize(_size+_delta))
      return FALSE;

  int idx = shouldGo(rObj);
  if (idx == -1) return FALSE;

  if (idx != _total)
  {
    for (int ii = _total; ii > idx; ii--)
      _entries[ii] = _entries[ii-1];
  }

  _entries[idx] = rObj;
  _total++;
  return TRUE;
}


// "remove" removes the first occurrence of an item equal to the specified
// item in the array.
//
template <class T> Bool CmTOrderedArray<T>::remove(const T& rObj)
{
  if (_total == 0) return FALSE;
  int  ii    = 0;
  Bool found = FALSE;
  while (ii < _total && !found)
    if (_entries[ii++] == rObj) found = TRUE;
  return (found) ? removeAt(ii-1) : FALSE;
}


// "removeAt" removes the item at the specified index.
//
template <class T> Bool CmTOrderedArray<T>::removeAt(int idx)
{
  if (idx < 0 || idx >= _total) return FALSE;

  for (int ii = idx; ii < _total-1; ii++)
    _entries[ii] = _entries[ii+1];
  _total--;
  return TRUE;
}


// "index" returns the index of the first occurrence of an item equal
// to the specified item.
//
template <class T> int CmTOrderedArray<T>::index(const T& rObj) const
{
  int  ii  = 0;
  int  idx = -1;
  while (ii < _total && idx == -1)
    if (_entries[ii++] == rObj) idx = ii-1;
  return idx;
}


// "shouldGo" reports the index where the specified object would be
// inserted if it were added to the array.
//
template <class T> int CmTOrderedArray<T>::shouldGo(const T& rObj) const
{
  if (_total == _size) return -1;

  if (_total == 0) return 0;
  if (rObj >= _entries[_total-1]) return _total;

  int idx = -1;
  int ii  = 0;
  while (ii < _total && idx == -1)
  {
    if (rObj < _entries[ii]) idx = ii;
    else                     ii++;
  }
  return idx;
}


// "lookup" returns the first occurrence of the item equal to the
// specified item in the array.
//
template <class T> const T& CmTOrderedArray<T>::lookup(const T& rObj) const
{
  int idx = index(rObj);
  return (idx > -1) ? _entries[idx] : _error;
}


// "contains" checks the array for an item equal to the input.
//
template <class T> Bool CmTOrderedArray<T>::contains(const T& rObj) const
{
  return (index(rObj) > -1) ? TRUE : FALSE;
}


// "occurrences" counts the number of occurrences of items equal to the
// specified item.
//
template <class T> unsigned CmTOrderedArray<T>::occurrences(const T& rObj) const
{
  int      ii  = 0;
  unsigned num = 0;
  while (ii < _total)
    if (_entries[ii++] == rObj) num++;
  return num;
}


// "resize" resizes the storage allocated for this array.
//
template <class T> Bool CmTOrderedArray<T>::resize(unsigned newSize)
{
  if (newSize == 0)
  {
    delete[] _entries;
    _entries = NULL;
    _size    = 0;
    _total   = 0;
    return TRUE;
  }

  T *newEntries = new T[newSize];
  if (!newEntries) return FALSE;

  if (newSize < _total) _total = newSize;

  for (int ii = 0; ii < _total; ii++)
    newEntries[ii] = _entries[ii];

  delete[] _entries;
  _entries = newEntries;
  _size    = newSize;
  return TRUE;
}


// "isEmpty" returns whether or not this array has any items in it.
//
template <class T> Bool CmTOrderedArray<T>::isEmpty() const
{
  return (_total == 0);
}


// "newIterator" creates and returns a new array iterator.
//
template <class T> CmTIterator<T>* CmTOrderedArray<T>::newIterator() const
{
  return new CmTOrderedArrayIterator<T>(*this);
}


// "copy" copies the items from the specified array into this array.
//
template <class T> void CmTOrderedArray<T>::copy(const CmTOrderedArray<T>& A)
{
  _size  = A._size;
  _total = A._total;
  _delta = A._delta;

  delete[] _entries;
  _entries = (_size > 0) ? new T[_size] : NULL;
  if (!_entries)
  {
    _total = 0;
    _size  = 0;
  }
  else
  {
    for (int ii = 0; ii < _total; ii++)
      _entries[ii] = A._entries[ii];
  }
}


// "done" returns whether or not this iterator can advance any further.
//
template <class T> Bool CmTOrderedArrayIterator<T>::done() const
{
  return (_index >= _array._total || _index < 0);
}


// "next" returns the current item in the array and advances the
// iterator to the next item.
//
template <class T> const T& CmTOrderedArrayIterator<T>::next()
{
  if (_index < _array._total) return _array._entries[_index++];
  else                        return _array._error;
}


// "previous" returns the current item in the array and decrements the
// iterator to the previous item.
//
template <class T> const T& CmTOrderedArrayIterator<T>::previous()
{
  if (_index >= 0) return _array._entries[_index--];
  else             return _array._error;
}


// "current" returns the current array item.
//
template <class T> const T& CmTOrderedArrayIterator<T>::current() const
{
  if (_index < _array._total) return _array._entries[_index];
  else                        return _array._error;
}


// "first" moves the iterator to the first item.
//
template <class T> void CmTOrderedArrayIterator<T>::first()
{
  _index = 0;
}


// "last" moves the iterator to the last item.
//
template <class T> void CmTOrderedArrayIterator<T>::last()
{
  _index = _array._total - 1;
}